class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        /*
        int len=nums.size();
        if(len<2){
            return len;
        }
        int max_len=0;
        vector<int> res(len,1);
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    res[i]=max(res[i],res[j]+1);
                }
                if(res[i]>max_len){
                    max_len=res[i];
                }
                //cout<<"i:"<<i+1<<",res:"<<res[i]<<",j:"<<j+1<<",res:"<<res[j]<<endl;
            }
        }
        return max_len;
        */
        int len=nums.size();
        vector<int> heap(len,0);
        int pocket=0;
        int left=0;
        int right=0;
        int heap_num=0;
        for(int i=0;i<len;i++){
            pocket=nums[i];
            left=0;
            right=heap_num;

            while(left<right){
                int mid=(left+right)/2;
                if(heap[mid]==pocket){
                    right=mid;
                } else if(heap[mid]>pocket){
                    right=mid;
                } else{
                    left=mid+1;
                }
            }

            if(left==heap_num){
                heap_num++;
            }
            heap[left]=pocket;
        }
        return heap_num;
    }
};

//town 2020.8.14
//dp[i] 以nums[i]结束的最长上升子序列
//dp[i]=max(dp[i],dp[j]+1) if nums[i]>nums[j] j=0,...,i-1
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        vector<int> dp(len,1);
        int max_len=0;
        for(int i=0;i<len;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }    
            }
            max_len=max(max_len,dp[i]);
        }
        return max_len;

    }
};